package com.leetcode.algorithm.y22.m07.w3;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 739. 每日温度
 * 
 * https://leetcode.cn/problems/daily-temperatures/
 * 
 * @author jie.deng
 *
 */
class Question0739Solution01 {

	public int[] dailyTemperatures(int[] temperatures) {
		// 单调栈
		Deque<Integer> stack = new ArrayDeque<Integer>();
		int len = temperatures.length;
		int[] answer = new int[len];
		for (int i = len - 1; i >= 0; i--) {
			int largerTemperatureIdx = add2AscStack(stack, temperatures, i);
			answer[i] = largerTemperatureIdx == 0 ? 0 : largerTemperatureIdx - i;
		}
		return answer;
	}

	private int add2AscStack(Deque<Integer> stack, int[] temperatures, int idx) {
		while (!stack.isEmpty() && temperatures[stack.peek().intValue()] <= temperatures[idx]) {
			stack.pop();
		}
		int retIdx = 0;
		if (!stack.isEmpty()) {
			retIdx = stack.peek().intValue();
		}
		stack.push(idx);
		return retIdx;
	}

}